﻿#include"heap.h"

void HpInit(Hp* hp, Datatype* b, int n)  //对使用传入的数组首元素地址和数组长度对堆中数组进行初始化（非原地）
{
	assert(hp);
	assert(hp->a);

	hp->capacity = 2*n;
	hp->size = 0;
	
	Datatype* tmp = (Datatype*)malloc(sizeof(Datatype) * 2 * n);
	if (tmp==NULL)
	{
		perror("malloc falil");
	}
	hp->a = tmp;

	for (int i = 0; i < n; i++)
	{
		HpPush(hp, b[i]);
	}
}

void HpDInit(Hp* hp, Datatype* f, int Datasize)  //在原地建堆初始化
{
	hp->a = f;
	hp->size = 0;
	hp->capacity = Datasize;

	for (int i = 0; i < Datasize; i++)
	{
		HpPush(hp, f[i]);
	}
}

void swap(Datatype* d, Datatype* e)  //交换d和e指向的变量的值
{
	Datatype tmp;

	tmp = *d;
	*d = *e;
	*e = tmp;
}

void AddHpUp(Datatype* a, int n, int child)  //向上调整函数：a为传入数组首元素，n为数组目前数据数量，child为需要向上调整的数据的下标
{
	//思路：1.找到父节点 2.比较父节点与子节点 2.选出较小数进行值交换 3.child=parent,将需要继续向上调整的父节点的小标给child，进行循环 4.循环继续的条件为child!=0

	while (child!=0)
	{
		int parent = (child - 1) / 2;
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
		}
		else
		{
			break;
		}
	}
}

void HpPush(Hp* hp, Datatype c)  //把数据c加入到堆中
{
	assert(hp);

	if (hp->size+1>hp->capacity)
	{
		printf("堆已满，无法再添加数据！\n");
	}
	else
	{
		hp->a[hp->size] = c;
		hp->size++;

		AddHpUp(hp->a, hp->size, hp->size - 1);
	}
}

void DelHpDown(Datatype* a, int size, int parent)  //向下调整函数：a为传入数组首元素地址，size为数组目前大小，parent为需要向下调整的数据的下标
{
	//思路：1.找到左右孩子 2.进行比较，找出左右孩子中值较小的节点与父节点比较 3.孩子节点比父节点小则交换值 4.parent=child,将孩子节点的下标给parent，使得继续向下调整 5.循环继续的条件为parent!=size-1
	while (parent<=size-1)
	{
		int leftchild = parent * 2 + 1;
		int rightchild = parent * 2 + 2;

		if (a[leftchild] < a[rightchild] && rightchild < size)   //默认leftchild为较小，否则交换
		{
			swap(&a[leftchild], &a[rightchild]);
		}
		if (a[leftchild] > a[parent] && leftchild < size)
		{
			swap(&a[leftchild], &a[parent]);
			parent = leftchild;
		}
		else
		{
		   break;
		}
	}	
}

void HpPop(Hp* hp)  //把根元素从堆中删除
{
	//思路：1.将根元素与尾部元素交换 2.处理size 3.将新的根元素向下调整
	swap(&hp->a[0], &hp->a[hp->size - 1]);

	hp->size--;

	DelHpDown(hp->a, hp->size, 0);
	
}

void HpPrintf(Datatype* a, int size)  //打印堆中的所有数据
{
	for (int i = 0; i < size; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void HpSort(Datatype* a, int size)  //使用堆对传入的数组a进行原地建堆排序
{
	Hp hp;
	//思路：1.原地建堆（升序建大堆） 2.循环：每次pop出堆内最大值到数组尾（直到size=1）
	HpDInit(&hp, a, size);

	for (int i = 0; i < size; i++)
	{
		HpPop(&hp);
	}
}